package Branch_And_Bound;

import java.io.*;
import java.util.*;

import Branch_And_Bound.Arc;
import hungary.Hungary;

/**
 * 分支定界法求TSP问题
 */

public class TSP {
    static int n; // 点的个数
    static int[][] dis; // 点之间的距离矩阵
    static alo_mode algorithm = alo_mode.hunagry; // 使用的定界算法
    static ArrayList<Arc> arcs = new ArrayList<>(); // 存储图中所有的边
    static ArrayList<Arc> best_tree = new ArrayList<>(); // 迄今为止找到最佳的解
    static int up = Integer.MAX_VALUE, low = 0; // 上下界
    // Kruscal算法中，front[i]表示在图中i点的根节点；hungary算法中，front[i]表示i节点前面的节点
    static int front[];
    static boolean x[][]; // x[i][j]表示边[i->j]是否使用（true表示此边作为分支条件被禁忌了，false表示此边不被禁忌）
    static boolean check[][]; // check[i][j]，避免在一条到底的分支定界中，重复定界几条边
    static boolean flag = false; // 标志，通过kruscal算法得到的one-tree是否可行
    static boolean vis[]; // 在匈牙利算法中使用的到，vis[i]标记此点i是否被访问过

    public static void main(String[] args) throws IOException, InterruptedException {
        // 读取算例（读出点的个数和距离矩阵就够了）
        // read_1();
        read_2();
        if (algorithm == alo_mode.Kruscal) {
            // 1.初始化解
            initX();

            // 2.计算边的集合，并排序
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    addArc(i, j, dis[i][j]);
                }
            }
            Sort(arcs);

            // 3.通过Kruskal计算one-tree：deg
            ArrayList<Arc> deg = kruskal();
            low = calculate(deg); // 其值为下界
            System.out.println(low);
            show1(deg);

            // 4.找出度大于等于3的点的边的集合：deg_3
            ArrayList<Arc> deg_3 = degree(deg);

            // 5.进行分支定界操作（对所有度大于等于3的边）
            for (int i = 0; i < deg_3.size(); i++) {
                // 5.1初始化解
                initX();
                if (check[deg_3.get(i).getFrom()][deg_3.get(i).getTo()]) continue;
                // 5.2分支定界处理
                branch_and_bound_tree(deg_3.get(i));

                check[deg_3.get(i).getFrom()][deg_3.get(i).getTo()] = true;
            }
            // 输出解
            System.out.println("*************** 得到的最优解：" + up + " ***************");
            show1(best_tree);
            feasibleTSP(best_tree);
        }
        else if (algorithm == alo_mode.hunagry) {
            // 先使用匈牙利算法求得一个解，以此作为下界
            ArrayList<HashMap<Integer, Integer>> sol = Hungary.exeHungary(dis);
            // 因为会得到不止一个解，所以可以对得到的解进行分别处理
            for (int i = 0; i < sol.size(); i++) {
                // 1.将hungary算法求得的解，转化成 front数组，并将当前解的值计算为下界
                Set<Integer> keys = sol.get(i).keySet();
                for (Integer k : keys) {
                    front[k - 1] = sol.get(i).get(k) - 1;
                }
                int now = 0;
                for (int j = 0; j < front.length; j++) {
                    now += dis[front[j]][j];
                }
                if (now > low) {
                    low = now;
                }

                // 2.开始进行分支操作，找到解中最小的闭环，进行分支操作
                ArrayList<Arc> arc_circle = get_circle();

                // 3.如果找的最小闭环中有所有的点，就说明此时已经找到了最优解，直接返回
                if (arc_circle.size() == n) {
                    System.out.println("最优解：");
                    feasibleTSP(arc_circle);
                    up = now;
                    return;
                }

                // 4.分支定界（以最小闭环中的边为分支条件）
                for (int j = 0; j < arc_circle.size(); j++) {
                    initX();
                    branch_and_bound_hungary(arc_circle.get(j));
                    // 这里为什么还要（我感觉这个意思就是说，一个闭环中，剪除一个边就行了，最好是让现成的两个边集合到一起）
                    check[arc_circle.get(j).getFrom()][arc_circle.get(j).getTo()] = true;
                }
                // 5.输出最优解
                System.out.println("最优解：");
                feasibleTSP(best_tree);
            }
        } else {
            System.out.println("暂未开发此算法");
        }
    }

    // 向边的集合中添加边
    public static void addArc(int i, int j, int dis) {
        arcs.add(new Arc(i, j, dis));
    }

    // 初始化解（所有的边都没有剪支禁忌）
    public static void initX() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                x[i][j] = false;
            }
        }
    }

    // Kruskal：返回one-tree
    public static ArrayList<Arc> kruskal() {
        flag = false;
        ArrayList<Arc> tree = new ArrayList<>();
        // 1.初始化所有点的根节点为其本身（起初每个点都是孤立的）
        for (int i = 0; i < front.length; i++) {
            front[i] = i;
        }

        // 2.构造不包含节点1的最小生成树
        int cnt = 0; // 用于记录最小生成树中边的个数
        for (int i = 0; i < arcs.size(); i++) { // 遍历边
            // 2.1 如果这个边包含节点1了，pass掉
            if (arcs.get(i).getFrom() == 0 || arcs.get(i).getTo() == 0) continue;
            // 2.2 如果此边已经作为剪支被禁忌了
            if (x[arcs.get(i).getFrom()][arcs.get(i).getTo()]) continue;
            // 2.3 在最小生成树中添加边（要求将所有的点都包含在连通图中）
            int fx = getFront(arcs.get(i).getFrom());
            int fy = getFront(arcs.get(i).getTo());
            if (fx != fy) {
                front[fy] = fx;
                cnt++;
                tree.add(new Arc(arcs.get(i)));
            }
        }
        // 若满足以下条件，则说明无可行解（因为此时找到的边的个数不足以联接所有的点）
        if (cnt < n - 2) {
            flag = true;
        }

        // 3.添加与1相连的两条边（将one节点与第2步中的最小生成树联接，构建one-tree）
        int min_1 = Integer.MAX_VALUE, min_2 = Integer.MAX_VALUE;
        int id1 = -1, id2 = -1; // 表示与1相连的两个点的编号，id1为最优的点，id2为次优的点
        boolean flag1 = false, flag2 = false; // true表示：1 -> 连通图
        for (int i = 1; i < n; i++) {
            // 如果这个点与0相连的边被分支禁忌了
            if (x[0][i] == true || x[i][0] == true) continue;
            // 先计算从0到i
            if (dis[0][i] < min_1) {
                min_2 = min_1;
                min_1 = dis[0][i];
                id2 = id1;
                id1 = i;
                flag2 = flag1;
                flag1 = true;
            } else {
                if (dis[0][i] < min_2) {
                    min_2 = dis[0][i];
                    id2 = i;
                    flag2 = true;
                } else {
                    // 再计算从i到0
                    if (dis[i][0] < min_1) {
                        min_2 = min_1;
                        min_1 = dis[i][0];
                        id2 = id1;
                        id1 = i;
                        flag2 = flag1;
                        flag1 = false;
                    } else if (dis[i][0] < min_2) {
                        min_2 = dis[i][0];
                        id2 = i;
                        flag2 = false;
                    }
                }
            }
        }
        // 将找出的两条边添加进去（必定是从0指向id，所以第二个要加取反）
        tree.add(new Arc((flag1 ? 0 : id1), (flag1 ? id1 : 0), dis[(flag1 ? 0 : id1)][(flag1 ? id1 : 0)])); // 0指向 最小生成树
        tree.add(new Arc((!flag2 ? 0 : id2), (!flag2 ? id2 : 0), dis[(!flag2 ? 0 : id2)][(!flag2 ? id2 : 0)])); // 最小生成树 指回0
        return tree;
    }

    // Kruskal: 获取node的根节点
    public static int getFront(int node) {
        if (front[node] == node) {
            return front[node];
        } else {
            return getFront(front[node]);
        }
    }

    // 对边的数组，根据边的权重大小进行排序
    public static void Sort(ArrayList<Arc> arcs1) {
        // 用于边排序，设计边的排序规则
        Comparator<Arc> comparator = new Comparator<Arc>() {
            @Override
            public int compare(Arc o1, Arc o2) {
                return (o1.getWeight() - o2.getWeight());
            }
        };
        Collections.sort(arcs1, comparator);
    }

    // Kruskal: 计算最小生成树的Cost
    public static int calculate(ArrayList<Arc> a) {
        int ans = 0;
        for (int i = 0; i < a.size(); i++) {
            ans += dis[a.get(i).getFrom()][a.get(i).getTo()];
        }
        return ans;
    }

    // Kruskal: 度大于等于3的点的边，a_tree为要寻找的最小生成树
    public static ArrayList<Arc> degree(ArrayList<Arc> a_tree) {
        ArrayList<Arc> a = new ArrayList<>();
        // 1.计算每个节点的度
        int du[] = new int[n];
        for (int i = 0; i < n; i++) {
            du[i] = 0;
        }
        for (int i = 0; i < a_tree.size(); i++) {
            du[a_tree.get(i).getFrom()]++;
            du[a_tree.get(i).getTo()]++;
        }

        // 2.找出度大于等于3的边，放入到集合a中
        for (int i = 0; i < n; i++) {
            if (du[i] >= 3) {
                for (int j = 0; j < a_tree.size(); j++) {
                    if (a_tree.get(j).getFrom() == i || a_tree.get(j).getTo() == i) {
                        if (!a.contains(a_tree.get(j))) {
                            a.add(new Arc(a_tree.get(j))); // 这里可能会出现重复的边
                        }
                    }
                }
            }
        }
        return a;
    }

    // Kruskal: 分支定界 one-tree（对边a分支，也就是禁忌边a）
    public static void branch_and_bound_tree(Arc a) {
        // 1.禁忌分支的边a，a后面的计算中就不能用了
        x[a.getFrom()][a.getTo()] = true;

        // 2.计算one-tree
        ArrayList<Arc> tmp1 = kruskal();

        // 3.判断是否为可行解，如果是不可行解，就直接剪支（flag=true的时候表示非可行解）
        if (flag) {
            System.out.println("-----------------不可行解----------------");
            x[a.getFrom()][a.getTo()] = false;
            show1(tmp1);
            return;
        }

        // 4.计算度大于等于3的点的边的集合
        ArrayList<Arc> tmp = degree(tmp1);

        // 5.定界操作
        int now = calculate(tmp1); // 当前操作的值
        // 5.1 如果当前值大于上界，那就直接剪支，不往下算了
        if (now > up) {
            x[a.getFrom()][a.getTo()] = false;
            System.out.println("-----------------超出上界----------------");
            show1(tmp1);
            return;
        }
        // 5.2 如果此时已经得到了TSP回路，则可以将此TSP回路的值作为上界
        if (tmp.size() == 0) {
            if (up > now && feasibleTSP(tmp1)) {
                up = now;
                copy(tmp1);
                System.out.println("----------------TSP可行解-----------------");
            } else {
                System.out.println("---------------TSP非可行解----------------");
            }
            show1(tmp1);
            feasibleTSP(tmp1);
            x[a.getFrom()][a.getTo()] = false;
            return;
        }
        // 5.3 其余情况下继续分支操作
        for (int i = 0; i < tmp.size(); i++) {
            if (check[tmp.get(i).getFrom()][tmp.get(i).getTo()]) continue;
            branch_and_bound_tree(tmp.get(i));
            check[tmp.get(i).getFrom()][tmp.get(i).getTo()] = true;
        }

        // 6.当分支操作到底后，需要将分支的边都解除禁忌
        for (int i = 0; i < tmp.size(); i++) {
            check[tmp.get(i).getFrom()][tmp.get(i).getTo()] = false;
        }
        x[a.getFrom()][a.getTo()] = false;
    }

    // 输出树的所有边
    public static void show1(ArrayList<Arc> aaa) {
        for (int i = 0; i < aaa.size(); i++) {
            System.out.println(aaa.get(i).getFrom() + "->" + aaa.get(i).getTo() + ", weight:" + aaa.get(i).getWeight());
        }
    }

    // 复制解
    public static void copy(ArrayList<Arc> aaa) {
        best_tree.clear();
        for (int i = 0; i < aaa.size(); i++) {
            best_tree.add(aaa.get(i));
        }
    }

    // Kruskal: 将解转化成TSP线路，并输出
    // 这个线路没必要是一条有向的直线，不同方向的距离差别，可以在距离矩阵中体现
    public static boolean feasibleTSP(ArrayList<Arc> aaa) {
        // 每个节点的前置节点
        int fa[] = new int[n];
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }
        for (int i = 0; i < aaa.size(); i++) {
            fa[aaa.get(i).getTo()] = aaa.get(i).getFrom();
        }
        int i = 0, num = 0;
        System.out.print("TSP路径：");
        while (true) {
            System.out.print(i + "<-");
            num++;
            if (fa[i] == i || num > n || fa[i] == 0) {
                break;
            }
            i = fa[i];
        }
        System.out.println();
        if (num == n) {
            return true;
        } else {
            return false;
        }
    }

    // hungary：返回最小闭环的边集合
    public static ArrayList<Arc> get_circle() {
        // 假设：将匈牙利算法求得的所有匹配连接到一起，必定得到闭环。一个或多个闭环。
        ArrayList<Arc> tmp = new ArrayList<>();
        ArrayList<Arc> ans = new ArrayList<>();
        // 起初所有点都未被放问过
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
        // 遍历每个节点，将所有边都加入进去
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue; // 如果已经访问过了，就跳过
            tmp.clear();
            int t = i;
            // 闭环
            while (!vis[t]) {
                vis[t] = true;
                tmp.add(new Arc(front[t], t, dis[front[t]][t]));
                t = front[t];
            }
            // vis[t] = true; // 这个可能是非必要的
            // 返回最小的一个闭环。这样既可以将最小的闭环融入到大闭环中，减少计算量。（如果是打破大闭环，会比打破大闭环计算量大）
            if (tmp.size() < ans.size() || ans.size() == 0) ans = (ArrayList<Arc>) tmp.clone();
        }
        return ans;
    }

    // hungary：分支定界（对边a进行分支）
    public static void branch_and_bound_hungary(Arc a) throws InterruptedException {
        // 1.先分支禁忌这条边
        x[a.getFrom()][a.getTo()] = true;
        // System.out.println("分支禁忌边：<" + a.getFrom() + "," + a.getTo() + ">");

        // 2.重新生成匈牙利成本矩阵 newDis
        int[][] newDis = new int[n][n];
        for (int i = 0; i < n; i++) {
            front[i] = i;
            for (int j = 0; j < n; j++) {
                // 1.如果这条边检查过
                // 不明白为什么这里需要让距离等于0呢
                if (check[i][j]) {
                    newDis[i][j] = 0;
                    continue;
                }
                // 2.如果这条边被分支禁忌了
                if (x[i][j]) {
                    newDis[i][j] = Integer.MAX_VALUE;
                }
                // 3.这条边没有他特殊的操作
                else {
                    newDis[i][j] = dis[i][j];
                }
            }
        }
        System.out.println("新生成的矩阵：");
        show(newDis);

        // 3.hungary算法计算
        ArrayList<HashMap<Integer, Integer>> sols = Hungary.exeHungary(newDis);
        // System.out.println("完成一次运算");
        for (int i = 0; i < sols.size(); i++) {
            // 3.1 HashMap类型的解转化成front[]数组类型
            Set<Integer> keys = sols.get(i).keySet();
            for (Integer k : keys) {
                front[sols.get(i).get(k) - 1] = k - 1;
            }

            // 3.2 计算求解的值，用于定界
            int now = 0;
            for (int j = 0; j < front.length; j++) {
                now += dis[front[j]][j];
            }
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (check[j][k]) {
                        now += dis[j][k];
                    }
                }
            }
            // 3.3 继续分支处理
            ArrayList<Arc> aaa = get_circle();
            // 3.3.1 如果大于上界，剪支
            if (now > up) {
                System.out.println("此解大于上界");
                x[a.getFrom()][a.getTo()] = false;
                return;
            }
            // 3.3.2 如果找到了一个完整的闭环，停止计算，到此为止
            if (aaa.size() == n) {
                // show1(aaa);
                System.out.println("此解为当前最优");
                if (feasibleTSP(aaa)) {
                    best_tree = (ArrayList<Arc>) aaa.clone();
                }
                x[a.getFrom()][a.getTo()] = false;
                up = now;
                return;
            }
            // 3.3.3 如果还有子环存在，继续分支定界
            else {
                for (int j = 0; j < aaa.size(); j++) {
                    System.out.println("禁忌了边：" + "<" + a.getFrom() + "," + a.getTo() + ">，后，继续禁忌" + "<" + aaa.get(j).getFrom() + "," + aaa.get(j).getTo() + ">");
                    branch_and_bound_hungary(aaa.get(j));
                    check[aaa.get(j).getFrom()][aaa.get(j).getTo()] = true;
                }
                for (int j = 0; j < aaa.size(); j++) {
                    check[aaa.get(j).getFrom()][aaa.get(j).getTo()] = false;
                }
            }
        }
    }

    // 读取算例（input.txt）
    public static void read_1() throws IOException {
        String line = "";
        String str[];
        BufferedReader br = new BufferedReader(new FileReader("src//data//hungary5.txt"));
        line = br.readLine();
        n = Integer.parseInt(line);
        System.out.println("点个数：" + n);
        dis = new int[n][n];
        front = new int[n];
        x = new boolean[n][n];
        check = new boolean[n][n];
        vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            line = br.readLine();
            str = line.split("\\s");
            for (int j = 0; j < n; j++) {
                dis[i][j] = Integer.parseInt(str[j]);
                System.out.print(dis[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 读取算例（a280.txt）
    public static void read_2() throws IOException {
        class node {
            int x;
            int y;

            public node(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
        ArrayList<node> nodes = new ArrayList<>();
        String line = "";
        BufferedReader br = new BufferedReader(new FileReader("src//data//a280.txt"));
        for (int i = 0; i < 6; i++) {
            br.readLine();
        }
        line = br.readLine();
        while (true) {
            line = line.trim();
            String strs[] = line.split("\\s+");
            nodes.add(new node(Integer.parseInt(strs[1]), Integer.parseInt(strs[2])));
            line = br.readLine();
            if (line.equals("EOF")) {
                break;
            }
        }
        n = nodes.size();
        System.out.println("点的个数：" + n);
        dis = new int[n][n];
        front = new int[n];
        x = new boolean[n][n];
        check = new boolean[n][n];
        vis = new boolean[n];
        // 计算距离矩阵
        for (int i = 0; i < n; i++) {
            dis[i][i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                dis[i][j] = (int) Math.sqrt((nodes.get(i).x - nodes.get(j).x) * (nodes.get(i).x - nodes.get(j).x) + (nodes.get(i).y - nodes.get(j).y) * (nodes.get(i).y - nodes.get(j).y));
                dis[j][i] = dis[i][j];
            }
        }
        // 输出矩阵
        System.out.println("距离矩阵：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(dis[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 打印出来矩阵
    public static void show(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

// 定界算法的枚举类
enum alo_mode {
    Kruscal, // 最小生成树
    hunagry // 匈牙利算法
}